/* *
* 核心思想是将待排序元素分到不同的桶中，然后对每个桶内的元素进行排序，最后将所有桶中的元素按照顺序依次取出，即可得到有序序列
* 桶排序的时间复杂度为O(n+k)，其中k为桶的个数，空间复杂度为O(n+k) 稳定
* 桶排序流程：
*  1.创建若干个桶；
*  2.将待排序元素分配到不同的桶中；
*  3.对每个桶内的元素进行排序；
*  4.按照桶的顺序依次输出所有元素，即得到有序序列。
* */

function bucketSort(arr, bucketSize = 3) {
    //? 1. 找到最大最小值 根据这个分桶(类似于计数排序)
    let min = Infinity
    let max = -Infinity
    for (let i = 0; i < arr.length; i ++) {
        if (arr[i] < min) min = arr[i]
        if (arr[i] > max) max = arr[i]
    }
    //? 计算桶数 这里要 + 1
    const bucketCount = Math.floor((max - min) / bucketSize) + 1
    //? 分空桶位置
    const buckets = new Array(bucketCount).fill(0).map(() => [])
    //? 2.根据值与min值的差距来分桶
    for (let i = 0; i < arr.length; i ++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i])
    }
    //? 3.对每个桶进行插入排序
    let startIndex = 0;
    for (let i = 0; i < buckets.length; i ++) {
        if (buckets[i].length > 0) {
            insertSort(buckets[i])
            //? 4.每对一个桶内元素排完后 更新原数组的排序
            for (let j = 0; j < buckets[i].length; j++) {
                arr[startIndex + j] = buckets[i][j];
            }
            startIndex += buckets[i].length;
        }

    }
    return arr
}


function insertSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    for (let i = 1; i < arr.length; i ++) {
        let j = i - 1
        let temp = arr[i]
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j]
            j--
        }
        arr[j + 1] = temp
    }
    return arr
}
const arr = [5,2,6,1,7,2,10,8]
console.log(bucketSort(arr));
